/**
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 * 最大路径和
 * 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * 路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。
 * @param root 
 */
const maxPathSum = (root: TreeNode | null): number => {
    // 边界判断
    if (root === null) return 0
    let ans = Number.MIN_SAFE_INTEGER;

    /**
     * 深度优先遍历
     * @param n 
     * @returns 
     */
    const dfs = (n: TreeNode | null): number => {
        // 如果为空, 那么就是空
        if (n === null) return 0

        // 只有节点的和大于0的时候, 才会选择对应的节点
        const leftSum = Math.max(dfs(n.left), 0)
        const rightSum = Math.max(dfs(n.right), 0)

        const sum = n.val + leftSum + rightSum

        // 计算最大值
        ans = Math.max(ans, sum)

        //! 该节点的最大贡献值
        return n.val + Math.max(leftSum, rightSum)
    }

    dfs(root)

    return ans
};